package leetcode_600;

import java.util.Arrays;

/**
 *@author 周杨
 *CoinChange2_518 给定硬币的大小 无限个硬币数量  问多少种形式 凑成给定sum
 *describe:用动态规划
 *2018年9月9日 下午8:59:37
 */
public class CoinChange2_518_ {
	public static void main(String[] args) {
		CoinChange2_518_ test=new CoinChange2_518_();
		System.out.println(test.change(5, new int[] {1,2,5}));
	}
	
	
	/**
	 * describe:动态规划 每次尝试多加入一枚硬币 利用上次硬币的保存的次数 AC 76%
	 * 2018年9月9日 下午8:59:08
	 */
	public int change(int amount, int[] coins) {
		if(amount==0)
			return 1;
		int dp[]=new int[amount+1];
		dp[0]=1;
		for(int i=0;i<coins.length;++i) {
			for(int j=1;j<=amount;++j) {
				if(coins[i]>j)
					continue;
				dp[j]+=dp[j-coins[i]];
			}
		}
		return dp[amount];
    }
	
	
	int res=0;
	int []coins;
	int amount;
	/**
	 * describe:回溯超时
	 * 2018年9月9日 下午8:21:48
	 */
	public int change1(int amount, int[] coins) {
		if(amount==0)
			return 1;
		Arrays.sort(coins);
        this.amount=amount;
        this.coins=coins;
        for(int i=0;i<coins.length;++i) {
        	if(coins[i]>amount)
        		break;
        	help(0,i);
        }
        return this.res;
    }
	
	public void help(int now,int index) {
		int temp=now+coins[index];
		if(temp>amount)
			return ;
		if(temp==amount) {
			++this.res;
			return ;
		}
		for(int i=index;i<coins.length;++i)
			help(temp,i);
		
	}
	
	
}
